%%
%% PURE FUNCTIONS for the core functionality
%% (except for local state and exceptions)
%%
functor
import
   Util
   TableT at 'Table.ozf'
   Expression
   Comparison
export
   Init
   Insert
   Update
   Delete
   Select

   AddTableTypes
   StripTableTypes
define
   %% INIT
   %% Create an empty database from a schema.
   fun {Init Schema}
      ExtendedSchema = {BuildSchema Schema}
   in
      database(schema:ExtendedSchema
	       tables:{Util.recordMap2 ExtendedSchema 
		       fun {$ Table} {Label Table.columns}#{TableT.new {KeyType Table}} end
		      }
	       references:{Util.recordMap2 ExtendedSchema
			   fun {$ Table}
			      {Label Table.columns}#{TableT.new {KeyType Table}}
			   end
			  }
	      )
   end

   %% UPDATE
   fun {Update Database Data Where}
      {AssertQueryValid Database update Data}
      {AssertForeignConstraints Database update Data}

      TableName = {Record.label Data}
      OldTable = Database.tables.TableName
      TableKey = {Key Database TableName}
      WhereFun = {CreateLocalWhereFun Database TableKey Where}
      ToBeUpdated = {WhereFun OldTable _}

      %% change the affected rows and simultanly update the references
      References = {NewCell Database.references}
      UpdatedRows = {TableT.map ToBeUpdated
		     fun {$ Row}
			NewRow = {Adjoin Row Data}
			OldRowPart = {Util.recordNarrow Row {Arity Data}}
		     in
			References := {UpdateReferences add Database
				       {UpdateReferences remove
					Database @References OldRowPart}
				       Data}
			NewRow
		     end
		    }
      %% integrate changed rows into database
      NewTable = {TableT.fold UpdatedRows
		  fun {$ T R}
		     {TableT.setRow T {KeyValue Database R} R}
		  end
		  OldTable
		 }
      NewTables = {AdjoinAt Database.tables TableName NewTable}
   in
      {AdjoinList Database [tables#NewTables references#@References]}
   end

   %% INSERT
   fun {Insert Database Data ?NewRow}
      NewSchema
      D = {AddAutoGeneratedColumns Data Database.schema ?NewSchema}
      {AssertQueryValid Database insert D}
      {AssertForeignConstraints Database insert D}

      TableName = {Record.label D}
      OldTable = Database.tables.TableName
      Id = {KeyValue Database D}

      NewReferences
      if {TableT.hasRow OldTable Id} then
	 raise database(command:insert table:TableName
			error:keyAlreadyInUsed(Id) data:D) end
      end
      %% add references to other tables
      NewReferences = {UpdateReferences add Database Database.references D}
      %% insert row
      NewTable = {TableT.setRow OldTable Id D}
      NewTables = {AdjoinAt Database.tables TableName NewTable}
   in
      NewRow = D
      {AdjoinList Database [tables#NewTables references#NewReferences schema#NewSchema]}
   end

   %% DELETE
   fun {Delete DB Table Where}
      if {Not {HasFeature DB.schema Table}} then
	 raise database(error:unknownTable(Table) command:delete) end
      end
      TableKey = {Key DB Table}
      WhereFun = {CreateLocalWhereFun DB TableKey Where}
      ToBeDeleted Remaining
      OldTable = DB.tables.Table
      {WhereFun OldTable Remaining ToBeDeleted}
      %% check whether we can delete all rows (no foreign keys)
      RefsToTable = DB.references.Table
      {TableT.forAllRows ToBeDeleted
       proc {$ Row}
	  RefsToRow = {TableT.condGetRow RefsToTable {KeyValue DB Row} references}
	  NonZeroRefs = {Record.filter RefsToRow fun {$ C} C > 0 end}
       in
	  if {Width NonZeroRefs} > 0 then
	     raise database(command:delete
			    error:cannotDeleteReferencedRow(Row referencedBy:NonZeroRefs))
	     end
	  end
       end
      }
      %% remove references by deletes rows
      NewReferences = {TableT.fold ToBeDeleted
		       fun {$ Refs Row}
			  {UpdateReferences remove DB Refs Row}
		       end
		       DB.references
		      }
   in
      {AdjoinList DB
       [tables#{AdjoinAt DB.tables Table Remaining}
	references#NewReferences
       ]}
   end

   %% SELECT
   %% Returns a list of rows.
   fun {Select DB Query}
      %% analyze
      Info = {AnalyzeQuery DB Query}
      Ts = Info.tables
      %% get a filtered, selection-restricted list for every table (includes columns which
      %% are only referenced by where/having conditions).
      %% RowSets :: [[row(table:table(col:Val))]]
      RowSets =
      {Map Ts
       fun {$ T} {SelectFromTable DB T Info.tableEquations.T Info.selectedColumns.T} end
      }
      %% CartesianRows :: [[row(table1:...) row(table2:...) ...]]
      %% TODO: merge join?
      CartesianRows = {Util.cartesianNProduct RowSets}
      %% JoinedRows: [row(table1:... table2:... ...)]
      JoinedRows = {Map CartesianRows Util.adjoinN}
      Filtered = {Filter JoinedRows Info.globalEquation}
      Aggregated = {Aggregate Info.aggregators Ts Info.groupColumns Filtered Info.countAll}
      HavingFiltered = {Filter Aggregated Info.havingEquation}
      %% remove columns that were included only for where/having conditions
      UnselectedRemoved = {FilterUnselectedColumns HavingFiltered Info.selectedColumns}
      DistinctRows = if Info.distinct then {Util.nub UnselectedRemoved}
		     else UnselectedRemoved end
      Sorted = case Info.sorter of nothing then DistinctRows
	       else {Sort DistinctRows Info.sorter}
	       end
   in
      Sorted
   end

   
   %% Support functions

   %% Support for Init
   local
      %% columnName(notNull references:tableName generated)
      %% ->
      %% columnName(notNull:notNull references:tableName generated:0)
      fun {BuildColumnSchema ColumnDesc}
	 {List.toRecord {Label ColumnDesc}
	  {Map {Record.toListInd ColumnDesc}
	   fun {$ I#F}
	      if F == generated then
		 if {Not {HasFeature ColumnDesc type}} then
		    raise
		       database(error:noTypeSpecifiedForAutoGeneratedColumn data:ColumnDesc)
		    end
		 end
		 if ColumnDesc.type \= int then
		    raise
		       database(error:autoGeneratedColumnsMustBeTypeInt data:ColumnDesc)
		    end
		 end
		 generated#0
	      elseif {IsInt I} then F#F
	      else I#F
	      end
	   end
	  }
	 }
      end

      %% item(id name(notNull))
      %% ->
      %% row(key:id columns:item(id:id name:name(notNull:notNull))
      fun {BuildTableSchema R}
	 row(key:{KeyDescOfRow R}
	     columns:
		{List.toRecord {Label R}
		 {Map {Record.toList {Record.subtractList R [primaryKey]}}
		  fun {$ Col} {Label Col}#{BuildColumnSchema Col} end
		 }
		})
      end
   in
      %% Creates a more efficiently accessible (but less terse) representation of a schema.
      %%
      %% schema(item(id name(notNull)))
      %% ->
      %% schema(item:row(key:id columns:item(id:id name:name(notNull:notNull))))
      fun {BuildSchema S}
	 %% TODO: check that foreign constraints make sense
	 {List.toRecord {Label S}
	  {Map {Record.toList S}
	   fun {$ Table}
	      {Record.label Table}#{BuildTableSchema Table}
	   end
	  }
	 }
      end
   end

   %% NewSchema: Schema with increased counters
   fun {AddAutoGeneratedColumns Data Schema ?NewSchema}
      TableName = {Label Data}
      NewData
      AutoCols = {Record.filter Schema.TableName.columns fun {$ C} {HasFeature C generated} end}
      NewSchemaCols
      NewTableDesc
   in
      NewData#NewSchemaCols =
      {Record.foldL AutoCols
       fun {$ D#S C}
	  ColumnName = {Label C}
	  NewColumnDesc
       in
	  if {HasFeature D ColumnName} then
	     raise database(command:insert error:autogeneratedColumnProvided data:Data) end
	  end
	  %% increase sequence in row scheme
	  NewColumnDesc = {AdjoinAt S.ColumnName generated C.generated+1}
	  %% add generated value to row
	  {AdjoinAt D ColumnName C.generated}#
	  %% replace column in row scheme
	  {AdjoinAt S ColumnName NewColumnDesc}
       end
       Data#Schema.TableName.columns
      }
      NewTableDesc = {AdjoinAt Schema.TableName columns NewSchemaCols}
      NewSchema = {AdjoinAt Schema TableName NewTableDesc}
      NewData
   end

   fun {ToExpressionList E}
      if {Expression.is E} then [E] else E end
   end
   
   %% Given a list of where-conditions and
   %% the name of the table's key, create a function that takes a table
   %% and returns the selected rows and binds the remaining rows to the second arg.
   %% Optimizations for empty where clauses and simple key comparison.
   fun {CreateLocalWhereFun DB KeyName Where}
      WhereConditions = {ToExpressionList Where}
      fun {IsMyKey C} {IsColumnDesc C} andthen C.1 == KeyName end
   in
      case WhereConditions
	 %% Return the whole tabel for empty where clause
      of nil then
	 fun {$ Table ?Others} Others = {TableT.cloneNew Table} Table end
	 %% Return a singleton record if where clause is comparison to key
      [] [[L '=' R]] andthen {IsMyKey L} andthen {Expression.isLiteral R}
	 orelse {IsMyKey R} andthen {Expression.isLiteral L} then
	 KeyVal = if {IsMyKey L} then R else L end
      in
	 fun {$ Table ?Others}
	    Others = {Value.byNeed %% costly, but not always needed
		      fun {$}
			 {TableT.filter Table fun {$ Row} {KeyValue DB Row} \= KeyVal end}
		      end}

	    if {TableT.hasRow Table KeyVal} then
	       {TableT.setRow {TableT.cloneNew Table} KeyVal {TableT.getRow Table KeyVal}}
	    else
	       {TableT.cloneNew Table}
	    end
	 end
      else %% Filter record with constructed filter function otherwise
	 RawWhereFun = {CreateWhereFun WhereConditions}
	 fun {WhereFun Row} L = {Label Row} in {RawWhereFun row(L:Row)} end
      in
	 fun {$ Table ?Others}
	    {TableT.partition Table WhereFun $ Others}
	 end
      end
   end

   %% Update references by foreign keys.
   %% Mode: add or remove
   fun {UpdateReferences Mode DB Refs What}
      Table = {Label What}
      Delta = case Mode of add then 1 [] remove then ~1 end
   in
      {FoldL {Columns DB Table}
       fun {$ R C}
	  Col = {Label C}
       in
	  if {HasFeature What Col} then
	     case {CondSelect DB.schema.Table.columns.Col references nothing}
	     of nothing then R
	     [] ReferencedTable then
		Id = What.Col
		OldRefsToRow = {TableT.condGetRow R.ReferencedTable Id references}
		OldRefsByThisTable = {CondSelect OldRefsToRow Table 0}
		NewRefsToRow = {AdjoinAt OldRefsToRow Table OldRefsByThisTable+Delta}
		NewRefsToTable = {TableT.setRow R.ReferencedTable Id NewRefsToRow}
	     in
		{AdjoinAt R ReferencedTable NewRefsToTable}
	     end
	  else
	     R
	  end
       end
       Refs
      }
   end
   
   %% Throws if one of the columns in Data is a foreign key and the key value does not exist.
   proc {AssertForeignConstraints Database CMD Data}
      TableName = {Label Data}
   in
      for C in {Columns Database TableName} do
	 if {HasFeature C references} then
	    ReferredTable = Database.tables.(C.references)
	    ThisColName = {Label C}
	 in
	    if {HasFeature Data ThisColName} andthen
	       {Not {TableT.hasRow ReferredTable Data.ThisColName}} then
	       raise
		  database(command:CMD
			   table:TableName
			   error:foreignKeyConstraintViolated(C)
			   data:Data)
	       end
	    end
	 end
      end
   end

   proc {AssertQueryValid DB CMD Data} %% CMD: insert or update
      proc {ThrowError E}
	 raise database(command:CMD
			table:TableName
			columns:{ColumnNames DB TableName}
			error:E
			data:Data)
	 end
      end      
      TableName = {Record.label Data}
      TableExists = {HasFeature DB.schema TableName}
      ColumnsCorrect =
      case CMD of insert then {Arity Data} == {ColumnNames DB TableName}
      [] update then
	 {Util.isSubset {Arity Data} {ColumnNames DB TableName}}
      end
      UpdateWithoutKey =
      case CMD of insert then true
      [] update then
	 {Util.none {Arity Data} fun {$ A} {BelongsToKey DB TableName A} end}
      end
   in
      if {Not TableExists} then {ThrowError tableDoesNotExist} end
      if {Not ColumnsCorrect} then {ThrowError incorrectColumns} end
      if {Not UpdateWithoutKey} then {ThrowError keyMustNotBeSpecifiedInUpdate} end
      %% check that no value is free and that nonNull constrains are observed
      {Record.forAllInd Data
       proc {$ C V}
	  if {IsFree V} then {ThrowError freeValuesNotAllowed(C V)} end
	  if {IsNotNull DB TableName C} andthen V == null then
	     {ThrowError notNullConstraintViolated(C)}
	  end
       end
      }
   end

   fun {IsNotNull DB T ColumnName}
      {BelongsToKey DB T ColumnName}
      orelse
      {HasFeature DB.schema.T.columns.ColumnName notNull}
   end


   %% Key access

   %% returns a tuple of the names of the columns that constitute the table's key
   %% or only a single column name
   fun {Key Database TableName}
      Database.schema.TableName.key
   end

   fun {KeyDescOfRow TableDesc}
      if {HasFeature TableDesc primaryKey} then
	 TableDesc.primaryKey
      else % first row by default
	 {Label TableDesc.1}
      end
   end

   fun {IsRealTuple X} case X of '#'(_ ...) then true else false end end
   
   fun {KeyValue Database Row}
      K = {Key Database {Label Row}}
   in
      if {IsRealTuple K} then
	 {Record.map K fun {$ KK} Row.KK end}
      else
	 Row.K
      end
   end

   fun {KeyType TableDesc}
      K = TableDesc.key
   in
      if {IsRealTuple K} then
	 {Record.map K
	  fun {$ KK}
	     if {Not {HasFeature TableDesc.columns.KK type}} then
		raise database(error:typeForKeyColumnNotSpecified(TableDesc KK)) end
	     end
	     TableDesc.columns.KK.type
	  end}
      else
	 if {Not {HasFeature TableDesc.columns.K type}} then
	    raise database(error:typeForKeyColumnNotSpecified(TableDesc K)) end
	 end
	 TableDesc.columns.K.type
      end
   end

   fun {BelongsToKey DB TableName ColumnName}
      K = {Key DB TableName}
   in
      ColumnName == K %% one-element key
      orelse {Member ColumnName {Record.toList K}}
   end


   %% columns

   fun {Columns Database TableName}
      {Record.toList Database.schema.TableName.columns}
   end

   fun {ColumnNames Database TableName}
      {Arity Database.schema.TableName.columns}
   end

   
   %% Support for Select
   
   fun {FilterUnselectedColumns Rows SCs}
      ReallySelectedColumns %% table->[columnAlias]
      = {Record.map SCs fun {$ Cs}
			   {Map {Filter Cs fun {$ _#_#B} B end}
			    fun {$ _#A#_} A end
			   }
			end
	}
   in
      {Map Rows
       fun {$ R}
	  {Record.map R
	   fun {$ Part}
	      if {Label Part} == count then Part
	      else
		 TableName = {Label Part}
		 TableColumns = ReallySelectedColumns.TableName 
	      in
		 {Record.filterInd Part
		  fun {$ I _} TableColumns == ['*'] orelse {Member I TableColumns} end
		 }
	      end
	   end
	  }
       end
      }
   end

   fun {CreateRowComparer ColumnNames}
      fun {$ Row1 Row2}
	 {All ColumnNames fun {$ C} {GetColVal Row1 C} == {GetColVal Row2 C} end}
      end
   end

   %% Aggregate
   local
      fun {ReplaceColumn Row ColumnDesc AggName With}
	 Table = {Label ColumnDesc}
	 OldPart = Row.Table
	 ColumnName = ColumnDesc.1
	 NewPart = {AdjoinAt OldPart ColumnName With}
      in
	 {AdjoinAt Row Table NewPart}
      end
      fun {MapFirst Xs Fun}
	 case Xs of X|Xr then {Fun X}|Xr
	 [] nil then nil
	 end
      end
   in
      fun {Aggregate Aggregators TableNames GroupColumns Rows CountAll}
	 case Aggregators of nil then Rows
	 else
	    Groups = {Util.groupBy {CreateRowComparer GroupColumns} Rows}
	    NewGroups =
	    {Map Groups %% for each group
	     fun {$ G}
		{FoldL Aggregators %% iteratively apply the aggregators on it
		 fun {$ CG ColumnDesc#AggName#Fun}
		    Res = {Fun ColumnDesc CG}
		 in
		    %% and update the first row to include the result
		    {MapFirst CG fun {$ Row} {ReplaceColumn Row ColumnDesc AggName Res} end}
		 end
		 G
		}
	     end
	    }
	 in
	    %% take the first row of every group, optionally add group count
	    {Map NewGroups
	     fun {$ G}
		FirstRow = G.1
	     in
		if CountAll then
		   {Adjoin FirstRow row(count:count('*':{Length G}))}
		else
		   FirstRow
		end
	     end}
	 end
      end
   end

   fun {SelectColumns Row SelectedColumns}
      case SelectedColumns of ['*'#_#_] then Row
      else
	 {List.toRecord {Label Row}
	  {Map SelectedColumns
	   fun {$ Col#ColAlias#_}
	      ColAlias#Row.Col
	   end
	  }
	 }
      end
   end

   fun {SelectFromTable DB TableName TableEqs SelectedColumns}
      FilteredRows = {TableT.toList {TableEqs DB.tables.TableName _}}
   in
      {Map FilteredRows
       fun {$ Row}
	  L = {Label Row}
       in
	  row(L:{SelectColumns Row SelectedColumns})
       end
      }
   end

   fun {IsColumnDesc L}
      {Expression.isVar L}
   end

   fun {GetColVal Row ColDesc}
      {Expression.eval ColDesc Row}
   end

   %% Create a row predicate from a list of conditions.
   fun {CreateWhereFun Cs}
      for C in Cs do
	 if {Not {Expression.is C}} then raise database(malformedExpression(C)) end end
      end
      fun {$ Row}
	 {All Cs fun {$ F} {Expression.eval F Row} end}
      end
   end

   local
      fun {LiftAggregator Fun}
	 fun {$ ColumnDesc Rows}
	    Xs = {Map Rows fun {$ R} {GetColVal R ColumnDesc} end}
	 in
	    case Xs of nil then null
	    else {Fun Xs}
	    end
	 end
      end

      fun {FilterNulls Xs}
	 {Filter Xs fun {$ X} X \= null end}
      end
   
      fun {Count Xs}
	 {Length {FilterNulls Xs}}
      end

      fun {CountDistinct Xs}
	 {Length {Util.nub {FilterNulls Xs}}}
      end
   in
      Aggregators = unit(avg:{LiftAggregator Util.avg}
			 count:{LiftAggregator Count}
			 countDistinct:{LiftAggregator CountDistinct}
			 max:{LiftAggregator Util.maximum}
			 min:{LiftAggregator Util.minimum}
			 sum:{LiftAggregator Util.sum}
			)
      AggregatorList = {Arity Aggregators}
   end

   fun {IsAggregator Column}
      {Member Column AggregatorList}
   end

   fun {AggColumnAlias AggName Column}
      if {HasFeature Column as} then Column.as
      else
	 {VirtualString.toAtom AggName#"("#Column#")"}
      end
   end

   %% Analyze a query to find out about
   %%  - involved tables
   %%  - a filter predicate on the whole row (does not include table-specific equatations)
   %%  - a filter predicate for 'having' (applied after aggregation)
   %%  - an optional sorting function
   %%  - columns that are involved in grouping (in case any aggregator is used)
   %%  - for every table:
   %%    * selected columns
   %%    * columns that are involed in the join
   %%    * a table-specific filter predicate
   %%    * an optional aggregator function for every column
   fun {AnalyzeQuery DB query(select:Sel0 where:W having:H orderBy:OB ...)}
      Distinct = {Util.recordMember distinct Sel0}
      CountAll = {Util.recordMember count('*') Sel0}
      Sel = {Record.filter Sel0 fun {$ F} F \= distinct andthen F \= count('*') end}
      Having = {ToExpressionList H}
      Where = {ToExpressionList W}
   
      %% Find out which columns are selected, what aggregate functions are used
      %% and which columns are involved in grouping (those which are nog aggregated)
      %% [ColumnDesc]
      GroupColumns = {NewCell nil}
      %% [ColumnDesc#AggName#AggFun]
      Aggs = {NewCell nil}
      %% table->[columnName#columnAlias#bool]
      Selections = {NewDictionary}
      {AnalyzeSelectors Sel GroupColumns Aggs Selections}

      fun {ColumnIsKnown T C ?OriginalName}
	 for ON#Col#_ in Selections.T return:R default:false do
	    if Col == C then OriginalName = ON {R true}
	    elseif Col == '*' then OriginalName = C {R true}
	    end
	 end
      end
      %% global equations: involve 2 distinct tables (or no table)
      GlobalEqs = {Filter Where IsGlobalCondition}

      %% append columns from global where conditions and having conditions
      %% (local where conditions are applied before selection)
      {AddColumnsFromConditions {Append GlobalEqs Having} Selections ColumnIsKnown}

      Tables = {Dictionary.keys Selections}
   
      {AssertNoDuplicateColumns Selections}
   
      fun {TableEquations T} %% Eqs that are local to T
	 MyExpressions = {Filter Where fun {$ W} Vars = {Expression.referencedVars W} in
					  Vars \= nil andthen
					  {All Vars
					   fun {$ V} {Expression.getVarScope V} == T end}
				       end}
	 WithReplacedAliases =
	 {Map MyExpressions
	  fun {$ E}
	     {Expression.mapVars E
	      fun {$ V} OriginalName in
		 if {ColumnIsKnown T {Expression.getVarName V} ?OriginalName} then
		    {Expression.newVar {Expression.getVarScope V} OriginalName}
		 else
		    V
		 end
	      end
	     }
	  end
	 }
      in
	 {CreateLocalWhereFun DB {Key DB T} WithReplacedAliases}
      end

      {AssertNoUnknownColumns {Append Where Having} DB ColumnIsKnown}
   in
      unit(tables:Tables
	   aggregators:@Aggs
	   groupColumns:@GroupColumns
	   sorter:{OrderBySorter OB}
	   selectedColumns:{Dictionary.toRecord unit Selections}
	   tableEquations:{Util.mapListToRecord unit Tables TableEquations}
	   globalEquation:{CreateWhereFun GlobalEqs}
	   havingEquation:{CreateWhereFun Having}
	   distinct:Distinct
	   countAll:CountAll
	  )
   end

   proc {AnalyzeSelectors Sel GroupColumns Aggs Selections}
      for T in {Arity Sel} do
	 TableName = {Label Sel.T} in
	 Selections.TableName := nil
	 for C in {Arity Sel.T} do
	    Col = Sel.T.C
	    ColName = {Label Col}
	 in
	    if {IsAggregator ColName} then
	       AggName = ColName
	       RealColName = {Label Col.1}
	       ColAlias = {AggColumnAlias AggName Col.1}
	       ColumnSpec = TableName(ColAlias)
	    in
	       Aggs := ColumnSpec#AggName#(Aggregators.AggName)|@Aggs
	       Selections.TableName := RealColName#ColAlias#true|Selections.TableName
	    else %% might be '*'
	       ColAlias = {CondSelect Col as ColName}
	    in
	       Selections.TableName := ColName#ColAlias#true|Selections.TableName
	       GroupColumns := TableName(ColAlias)|@GroupColumns
	    end
	 end
      end
   end

   fun {IsGlobalCondition C}
      ReferencedTables = {Expression.referencedScopes C}
   in
      {Length ReferencedTables} \= 1
   end

   fun {ReferencedColumns Condition}
      {Filter {Expression.referencedVars Condition} fun {$ X} X \= count('*') end}
   end
   
   proc {AddColumnsFromConditions Cs Selections ColumnIsKnown}
      for C in Cs do
	 for V in {ReferencedColumns C} do
	    TableName = {Expression.getVarScope V}
	    ColumnName = {Expression.getVarName V}
	 in
	    if {Not {ColumnIsKnown TableName ColumnName _}} then
	       Selections.TableName := ColumnName#ColumnName#false|Selections.TableName
	    end
	 end
      end
   end

   proc {AssertNoDuplicateColumns Selections}
      for TableCols in {Dictionary.items Selections} do
	 ColDict = {NewDictionary} in
	 for _#ColAlias#_ in TableCols do
	    if {HasFeature ColDict ColAlias} then
	       raise database(command:select error:duplicateColumn(ColAlias)) end
	    end
	    ColDict.ColAlias := unit
	 end
      end
   end
   
   fun {OrderBySorter OB} %% create a <-operator from a list of sorting criteria
      case OB of nothing then nothing
      else
	 OBs = if {IsList OB} then OB else [OB] end
	 OperandsAndOperators
	 = {Map OBs
	    fun {$ OB}
	       if {Label OB} == desc then OB.1#Comparison.'>'
	       elseif {Label OB} == asc then OB.1#Comparison.'<'
	       else OB#Comparison.'<'
	       end
	    end
	   }
      in
	 fun {$ Row1 Row2}
	    for OrderBy#Op in OperandsAndOperators return:R default:false do
	       Op1 = {GetColVal Row1 OrderBy}
	       Op2 = {GetColVal Row2 OrderBy}
	    in
	       if {Op Op1 Op2} then {R true}
	       elseif Op1 == Op2 then skip
	       else {R false}
	       end
	    end
	 end
      end
   end

   proc {AssertNoUnknownColumns Cs DB ColumnIsKnown}
      for C in Cs do
	 for V in {ReferencedColumns C} do
	    TableName = {Expression.getVarScope V}
	    ColumnName = {Expression.getVarName V}
	 in
	    if {Not {HasFeature DB.schema TableName}} orelse
	       ({Not {HasFeature DB.schema.TableName.columns ColumnName}}
		andthen {Not {ColumnIsKnown TableName ColumnName _}}) then
	       raise database(command:select error:unknownColumn(ColumnName)) end
	    end
	 end
      end
   end

   %%
   
   %% remove tree type from tables (i.e. strip the program code for saving)
   fun {StripTableTypes DB}
      NewTables = {Record.map DB.tables TableT.removeType}
      NewRefs = {Record.map DB.references TableT.removeType}   
   in
      {AdjoinList DB [tables#NewTables references#NewRefs]}
   end

   %% add tree type to tables (after loading)
   fun {AddTableTypes DB}
      NewTables = {Record.mapInd DB.tables
		   fun {$ TN T} {TableT.addType T {KeyType DB.schema.TN}} end
		  }
      NewRefs = {Record.mapInd DB.references
		 fun {$ TN T} {TableT.addType T {KeyType DB.schema.TN}} end
		}
   in
      {AdjoinList DB [tables#NewTables references#NewRefs]}
   end
end
